題目

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.

題意

給定符號(, ), {, }, [ 以及 ]。

通過驗證的條件：

1. 右括號需對應到相同類型的左括號
2. 右括號對應的順序需正確

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "()[]{}"
Output: true

Example 3:

Input: s = "(]"
Output: false

Example 4:

Input: s = "([)]"
Output: false

Example 5:

Input: s = "{[]}"
Output: true

解題步驟

可使用堆疊(stack)後進先出Last in, first out (LIFO)的概念，遇到左括號先放入stack，遇到右括號
就從stack的最後一個開始比對。

宣告左右括號陣列：

let left = ['(', '[', '{'];
let right = [')', ']', '}'];

宣告匹配的物件，比對之用：

let match = {
    ')': '(',
    ']': '[',
    '}': '{'
}

遇到左括號，放入stack：

if (left.indexOf(s[i]) > -1) {
    stack.push(s[i]);
}

遇到右括號，從stack最後一個取出配對：

if (right.indexOf(s[i]) > -1) {
    let stackStr = stack.pop();
    if (match[s[i]] != stackStr) {
        return false;
    }
}

Solution

let isValid = function (s) {
  if (!s) return true;

  let stack = [];

  let left = ['(', '[', '{'];
  let right = [')', ']', '}'];
  let match = {
    ')': '(',
    ']': '[',
    '}': '{'
  }

  for (let i in s) {
    if (left.indexOf(s[i]) > -1) {
      stack.push(s[i]);
    }

    if (right.indexOf(s[i]) > -1) {
      let stackStr = stack.pop();
      if (match[s[i]] != stackStr) {
        return false;
      }
    }
  }
  return stack.length == 0;
};